The RSA Group is Pseudo-Free
Identifieur interne : 000096 ( Main/Exploration ); précédent : 000095; suivant : 000097The RSA Group is Pseudo-Free
Auteurs : Daniele Micciancio [États-Unis]Source :
- Journal of Cryptology [ 0933-2790 ] ; 2010-04-01.
English descriptors
Abstract
Abstract: We prove, under the strong RSA assumption, that the group of invertible integers modulo the product of two safe primes is pseudo-free. More specifically, no polynomial-time algorithm can output (with non negligible probability) an unsatisfiable system of equations over the free Abelian group generated by the symbols g 1,…,g n, together with a solution modulo the product of two randomly chosen safe primes when g 1,…,g n are instantiated to randomly chosen quadratic residues. Ours is the first provably secure construction of pseudo-free Abelian groups under a standard cryptographic assumption and resolves a conjecture of Rivest (Theory of Cryptography Conference—Proceedings of TCC 2004, LNCS, vol. 2951, pp. 505–521, 2004).
Url:
DOI: 10.1007/s00145-009-9042-5
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000109
- to stream Istex, to step Curation: 000108
- to stream Istex, to step Checkpoint: 000088
- to stream Main, to step Merge: 000097
- to stream Main, to step Curation: 000096
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">The RSA Group is Pseudo-Free</title>
<author><name sortKey="Micciancio, Daniele" sort="Micciancio, Daniele" uniqKey="Micciancio D" first="Daniele" last="Micciancio">Daniele Micciancio</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:50B0AE4EE6B8CE5A800924C98FC9263D2046C134</idno>
<date when="2009" year="2009">2009</date>
<idno type="doi">10.1007/s00145-009-9042-5</idno>
<idno type="url">https://api.istex.fr/document/50B0AE4EE6B8CE5A800924C98FC9263D2046C134/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000109</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000109</idno>
<idno type="wicri:Area/Istex/Curation">000108</idno>
<idno type="wicri:Area/Istex/Checkpoint">000088</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000088</idno>
<idno type="wicri:doubleKey">0933-2790:2009:Micciancio D:the:rsa:group</idno>
<idno type="wicri:Area/Main/Merge">000097</idno>
<idno type="wicri:Area/Main/Curation">000096</idno>
<idno type="wicri:Area/Main/Exploration">000096</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">The RSA Group is Pseudo-Free</title>
<author><name sortKey="Micciancio, Daniele" sort="Micciancio, Daniele" uniqKey="Micciancio D" first="Daniele" last="Micciancio">Daniele Micciancio</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science and Engineering, University of California at San Diego, 92093, La Jolla, CA</wicri:regionArea>
<placeName><region type="state">Californie</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Journal of Cryptology</title>
<title level="j" type="abbrev">J Cryptol</title>
<idno type="ISSN">0933-2790</idno>
<idno type="eISSN">1432-1378</idno>
<imprint><publisher>Springer-Verlag</publisher>
<pubPlace>New York</pubPlace>
<date type="published" when="2010-04-01">2010-04-01</date>
<biblScope unit="volume">23</biblScope>
<biblScope unit="issue">2</biblScope>
<biblScope unit="page" from="169">169</biblScope>
<biblScope unit="page" to="186">186</biblScope>
</imprint>
<idno type="ISSN">0933-2790</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0933-2790</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Cryptographic assumptions</term>
<term>Pseudo-free Abelian group</term>
<term>Safe primes</term>
<term>Strong RSA problem</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We prove, under the strong RSA assumption, that the group of invertible integers modulo the product of two safe primes is pseudo-free. More specifically, no polynomial-time algorithm can output (with non negligible probability) an unsatisfiable system of equations over the free Abelian group generated by the symbols g 1,…,g n, together with a solution modulo the product of two randomly chosen safe primes when g 1,…,g n are instantiated to randomly chosen quadratic residues. Ours is the first provably secure construction of pseudo-free Abelian groups under a standard cryptographic assumption and resolves a conjecture of Rivest (Theory of Cryptography Conference—Proceedings of TCC 2004, LNCS, vol. 2951, pp. 505–521, 2004).</div>
</front>
</TEI>
<affiliations><list><country><li>États-Unis</li>
</country>
<region><li>Californie</li>
</region>
</list>
<tree><country name="États-Unis"><region name="Californie"><name sortKey="Micciancio, Daniele" sort="Micciancio, Daniele" uniqKey="Micciancio D" first="Daniele" last="Micciancio">Daniele Micciancio</name>
</region>
<name sortKey="Micciancio, Daniele" sort="Micciancio, Daniele" uniqKey="Micciancio D" first="Daniele" last="Micciancio">Daniele Micciancio</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Mathematiques/explor/SophieGermainV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000096 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000096 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Mathematiques |area= SophieGermainV1 |flux= Main |étape= Exploration |type= RBID |clé= ISTEX:50B0AE4EE6B8CE5A800924C98FC9263D2046C134 |texte= The RSA Group is Pseudo-Free }}
This area was generated with Dilib version V0.6.33. |